| 翻訳と辞書 |
| Gödel numbering for sequences ： ウィキペディア英語版 |
Gödel numbering for sequences
In mathematics, a Gödel numbering for sequences provides us an effective way to represent each finite sequence of natural numbers as a single natural number. Of course, the embedding is surely possible set theoretically, but the emphasis is on the effectiveness of the functions manipulating such representations of sequences: the operations on sequences (accessing individual members, concatenation) can be "implemented" using total recursive functions, and in fact by primitive recursive functions.
It is usually used to build sequential “data types” in the realm of arithmetic-based formalizations of some fundamental notions of mathematics. It is a specific case of the more general idea of Gödel numbering.
E.g. recursive function theory can be regarded as a formalization of notion “algorithm”, and if we regard it as a programming language, we can mimic arrays, lists by encoding a sequence of natural numbers in a single natural number — to achieve this, we can use various number theoretic ideas. Using the fundamental theorem of arithmetic is a straightforward way, but there are also more economic approaches, e.g. using pairing function combined with Chinese remainder theorem in a sophisticated way.〔Monk 1976: 56–58〕〔Csirmaz 1994: 99–100 (see (online ))〕
== Gödel numbering ==
(詳細はmutually exclusive or one-to-one correspondence with the sequences), we can use it to encode whole “architectures” of sophisticated “machines”. For example we can encode Markov algorithms,〔Monk 1976: 72–74〕 or Turing machines〔Monk 1976: 52–55〕 into natural numbers and thereby prove that the expressing power of recursive function theory is no less than that of the former machine-like formalizations of algorithms.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Gödel numbering for sequences」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|